package FourthWeek;


import java.util.ArrayList;
import java.util.List;

public class Thursday {
    int[] tmp3;
    public int reversePairs2(int[] nums) {
        int n = nums.length;
        tmp3 = new int[n];
        return mergeSort3(nums,0,n - 1);
    }

    public int mergeSort3(int[] nums,int left,int right) {
        if (left >= right) {
            return 0;
        }
        // 记录翻转对的个数
        int ret = 0;

        // 按照 归并排序 进行处理
        int mid = (left + right) / 2;

        // 处理左右两边。进行划分
        // 左面有多少个翻转对
        ret += mergeSort3(nums,left,mid);
        // 右面有多少个翻转对
        ret += mergeSort3(nums,mid + 1,right);

        // 计算 翻转对 的个数
        // // 降序处理
        // // 计算当前元素后面，有多少个元素的二倍比我小
        // // 固定 cur1，找cur2这部分
        // int cur1 = left,cur2 = mid + 1,i = 0;
        // while(cur1 <= mid) {
        //     while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) {
        //         // cur2的数据的二倍比cur1的数据大，cur2往后移动
        //         cur2++;
        //     }
        //     if (cur2 > right) {
        //         break;
        //     }
        //     ret += right - cur2 + 1;
        //     cur1++;
        // }

        // 升序处理
        // 计算当前元素之前，有多少个元素的一半比我大
        // 固定cur2，找cur1这部分
        int cur1 = left,cur2 = mid + 1,i = 0;
        while(cur2 <= right) {
            while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) {
                // cur2的数据的二倍比cur1的数据大，cur2往后移动
                cur1++;
            }
            if (cur1 > mid) {
                break;
            }
            ret += mid - cur1 + 1;
            cur2++;
        }

        // 对其有序数组进行逆序排序
        cur1 = left;
        cur2 = mid + 1;
        // // 降序处理
        // while(cur1 <= mid && cur2 <= right) {
        //     tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        // }
        // 升序处理
        while(cur1 <= mid && cur2 <= right) {
            tmp3[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        // 对于剩余数据进行处理
        while (cur1 <= mid) {
            tmp3[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tmp3[i++] = nums[cur2++];
        }

        // 把tmp的数据返回给nums进行有序拼接
        for (int j = left;j <= right;j++) {
            nums[j] = tmp3[j - left];
        }

        return ret;
    }


    // 315、计算右侧小于当前元素的个数
    int[] ret; // 接收由nums计算之后的数组，比如示例中的[2,1,1,0]
    int[] index; // 代表的原数组nums的数据的下标
    int[] tmpNums; // 使用这个数组把两个有序数组连接在一起
    int[] tmpIndex; // 这个数组也是同样的作用

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpNums = new int[n];
        tmpIndex = new int[n];
        // 初始化index这个原数组的下标
        for (int i = 0;i < n;i++) {
            index[i] = i;
        }
        // 根据nums的数据对ret进行处理
        mergeSort2(nums,0,n - 1);

        List<Integer> counts = new ArrayList<>();
        for (int x : ret) {
            counts.add(x);
        }
        return counts;
    }

    public void mergeSort2(int[] nums,int left,int right) {
        if (left >= right) {
            return;
        }
        // 按照 归并排序 进行处理
        // 得到中值
        int mid = (left + right) / 2;

        // [left,mid] [mid+1,right]
        // 处理左右两边
        mergeSort2(nums,left,mid);
        mergeSort2(nums,mid + 1,right);

        // 处理一左一右的情况
        int cur1 = left,cur2 = mid + 1,i = 0;
        while (cur1 <= mid && cur2 <= right) { // 降序处理
            if(nums[cur1] <= nums[cur2]) {
                tmpNums[i] = nums[cur2]; // 数据
                tmpIndex[i++] = index[cur2++]; // 数据对应的下标
            }else {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }

        // 处理一下边界情况
        while(cur1 <= mid) {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while(cur2 <= right) {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        // 把排完序的tmpRet和tmpIndex都放进nums和index中
        for (int j = left;j <= right;j++) {
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }
    }


    //LCR 170.交易逆序对的个数
    int[] tmp1;
    public int reversePairs(int[] record) {
        int n = record.length;
        tmp1 = new int[n];
        return mergeSort1(record,0,n - 1);
    }

    public int mergeSort1(int[] record,int left,int right) {
        if (left >= right) {
            return 0;
        }

        int ret = 0;

        // 使用归并排序
        // 计算中值
        int mid = (left + right) / 2;

        // 左半部分的逆序个数+排序
        ret += mergeSort1(record,left,mid);
        // 右半部分的逆序个数+排序
        ret += mergeSort1(record,mid + 1,right);

        // 一左一右+排序
        int cur1 = left,cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right) { // 数组排序完为升序的情况，找大值
            if (record[cur1] <= record[cur2]) {
                tmp1[i++] = record[cur1++];
            }else {
                ret += mid - cur1 + 1;
                tmp1[i++] = record[cur2++];
            }
        }
//        while(cur1 <= mid && cur2 <= right) {
//            if (record[cur1] <= record[cur2]) { // 数组为降序的时候，找小
//                tmp[i++] = record[cur2++];
//            }else {
//                ret += right - cur2 + 1;
//                tmp[i++] = record[cur1++];
//            }
//        }

        // 排序，加上对record进行处理
        while (cur1 <= mid) {
            tmp1[i++] = record[cur1++];
        }
        while (cur2 <= right) {
            tmp1[i++] = record[cur2++];
        }

        for (int j = left;j <= right;j++) {
            record[j] = tmp1[j - left];
        }

        return ret;
    }


    // 912.排序数组
    // 归并排序
    // 这个是缓存数组
    int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];

        mergeSort(nums,0,nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums,int left,int right) {
        if(left >= right) {
            // 递归结束条件
            return;
        }

        // 把整个数组分成两份进行处理，根据中间节点
        int mid = (left + right) / 2;

        // 先把左右两个区间进行排序
        // [left,mid] [mid+1,right]
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);

        // 把排序后的左右两个和并成一个数组
        // 使用双指针排序
        int cur1 = left,cur2 = mid + 1,i = 0;
        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while(cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }

        // 进行把tmp中的数据进行还原给nums，tmp是从0开始的
        for (int j = left;j <= right;j++) {
            nums[j] = tmp[j - left];
        }
    }
}
